package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-04-26 22:00
 */
public class QLint633 {
    public int findDuplicate(int[] nums) {
        if(nums == null || nums.length == 0) {
            return -1;
        }

        int slow = nums[0], fast = nums[nums[0]];
        while(true) {
            slow = nums[slow];
            fast = nums[nums[fast]];

            if(slow == fast) {
                slow = nums[0];
                fast = nums[fast];

                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[fast];
                }

                return fast;
            }
        }

    }
}
